package com.qezhhnjy.leetcode.question.tree;

import com.qezhhnjy.leetcode.entity.TreeNode;

/**
 * @author qezhhnjy
 * @date 2020/12/19-0:13
 * <p>
 * 递增顺序查找树
 * 给你一个树，请你 按中序遍历 重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
 * <p>
 * 提示：
 * 给定树中的结点数介于 1 和 100 之间。
 * 每个结点都有一个从 0 到 1000 范围内的唯一整数值。
 */
public class IncreaseOrderSearchTree {

    public TreeNode result = new TreeNode();

    // 设定 指针
    public TreeNode cursor = result;

    public TreeNode increasingBST(TreeNode root) {
        if (root == null) return null;

        increasingBST(root.left);
        root.left = null;
        cursor.right = root;
        // 移动指针
        cursor = root;
        increasingBST(root.right);
        return result.right;
    }

}
